/*
2021-11-12
https://leetcode-cn.com/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/
*/ 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        vector<int>ans(2,-1);
        int st=-1,ed=-2;
        int pre=-1;
        int idx=2;
        ListNode* p=head->next;
        if(p==NULL) return ans;
        ListNode* q=p->next;
        if(q==NULL) return ans;
        ans[0]=1e9;
        while(q!=NULL)
        {
            if((p->val>head->val && p->val>q->val) || (p->val<head->val && p->val<q->val))
            {
                if(st<0) st=idx;
                ed=idx;
                if(pre>=0) ans[0]=min(ans[0],idx-pre);
                pre=idx;
            }
            head=head->next;
            p=p->next;
            q=q->next;
            idx++;
        }
        ans[1]=ed-st;
        if(ed==st) ans[1]=-1;
        if(ans[0]==1e9) ans[0]=-1;
        return ans;
    }
};
